/**
 * FileName: DepthFirstSearch
 * Author:   powersi
 * Date:     2021/1/13 7:57
 * Description: dfs
 */
package com.zm.demo.core.leetcode.search;

import java.util.LinkedList;

/**
 * Description: dfs
 * Author:      powersi
 * Date:        2021/1/13 7:57
 */
public class DepthFirstSearch {

    static Boolean found = false;

    public static void main(String[] args) {
        Graph graph = new Graph(9);
        graph.buildGraph();

        dfs(1, 5, graph.getAdj());

    }

    /**
     * 从s点开始搜索到t的路径
     * @param s
     * @param t
     * @param adj
     * @return
     */
    public static void dfs(int s, int t, LinkedList<Integer>[] adj){

        if (s == t){
            return;
        }

        int [] prev = new int[9];
        for (int i = 0; i < 9; i++) {
            prev[i] = -1;
        }

        boolean visited[] = new boolean[9];
        visited[s] = true;

        dfs(s, t, adj, prev, visited);
        print(prev, s, t);
    }

    private static void dfs(int w, int t, LinkedList<Integer>[] adj, int[] prev, boolean[] visited) {
        if (found){
            return;
        }
        visited[w] = true;
        if (w == t){
            found = true;
            return;
        }
        for (int i = 0; i < adj[w].size() ; i++) {
            int q = adj[w].get(i);
            if (!visited[q]){
                prev[q] = w;
                dfs(q, t, adj, prev, visited);
            }

        }
    }

    public static void print(int[] prev, int s, int t){
        if (s!=t && prev[t]!= -1){
            print(prev, s, prev[t]);
        }
        System.out.println(" " + t );
    }
}
